// Package day_06_prefix_tree prefix_tree
// @Title day_06_prefix_tree
// @Description  前缀树的基本实现 基础功能: 增 删 查
// @Author  == 琳琳也叫王木木 ==  2021/9/1 13:48
// @Create  2021/9/1 13:48
package day_06_prefix_tree

type Trie struct {
	Pass int
	End  int
	Next []*Trie
}

// Constructor /** Initialize your data structure here.  初始化前缀树对象*/
func Constructor() Trie {
	return Trie{End: 0, Pass: 0, Next: make([]*Trie, 26)}
}

// Insert /** Inserts a word into the trie.向前缀树中插入字符串 word 。 */
func (this *Trie) Insert(word string) {
	// 判断字符串是否为空
	if len(word) < 1 || word == "" {
		return
	}
	this.Pass++
	for i := 0; i < len(word); i++ {
		index := byte(word[i]) - 'a' // 用数组存 获取他在26个英文字母中的对应下标
		// 如果没有指向对应的节点就创建一个
		if this.Next[index] == nil {
			this.Next[index] = &Trie{End: 0, Pass: 0, Next: make([]*Trie, 26)}
		}
		this = this.Next[index]
		this.Pass++
	}
	this.End++
}

// Search /** Returns if the word is in the trie.  如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。*/
func (this *Trie) Search(word string) bool {
	if len(word) < 1 || word == "" {
		return false
	}
	for i := 0; i < len(word); i++ {
		index := byte(word[i]) - 'a'
		for this.Next[index] == nil {
			return false
		}
		this = this.Next[index]
	}
	if this.End >= 1 {
		return true
	}
	return false
}

// StartsWith /** Returns if there is any word in the trie that starts with the given prefix. 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。*/
func (this *Trie) StartsWith(prefix string) bool {
	if len(prefix) < 1 || prefix == "" {
		return false
	}
	for i := 0; i < len(prefix); i++ {
		index := byte(prefix[i]) - 'a'
		for this.Next[index] == nil {
			return false
		}
		this = this.Next[index]
	}
	return true
}

func (this *Trie) Delete(word string) bool {
	if this.Search(word) == true {
		// 确保在前缀树中能搜索到对应的单词才去搜索
		return true
	}
	return false
}
